APP processing
APP stands for "a posteriori probability"; the acronym MAP, which stands for "maximum a posteriori", is also commonly used in the literature to refer to the same concept, though perhaps somewhat erroneously. An APP process is something that accepts input probabilities associated with some entities such as bits, symbols, states, etc., and using knowledge of the "constraints" placed on the entities, determines output probabilities for these entities. One or more constraints are grouped to form a constraint set.
As a specific example of how APP processing is applied, consider a set of bits known to have even parity (i.e. the total number of `1` bits in the set is even), and consider having a probability associated with being a `0` (as opposed to a `1`). Such probability values are output by a demodulator of a modem, for instance. These probability values are provided as input data into an APP process, and the APP process provides an adjusted probability for each bit, the output probabilities taking into account the known constraints. In the present example, the known constraint is that when corrected the set of bits has even parity. Referring to FIG. 2, an illustration of APP decoding of a set of three bits known to have even parity is shown.
The APP calculations for this three-bit example are as follows.
Let p.sub.i represent the input probability that the i-th bit is a `0` bit. PA0 Let r.sub.i represent the output (result) probability that the i-th bit is a `0` bit. PA0 Let q.sub.i represent the probability, calculated using the input probabilities, that all bits, excluding the i-th bit, have even parity. Note that q.sub.i is a likelihood associated with the i-th bit, derived from all bits except the i-th bit. PA0 p.sub.1 =0.5 PA0 p.sub.2 =0.6 PA0 p.sub.3 =0.7 PA0 q.sub.1 =p.sub.2 *p.sub.3 +(1-p.sub.2)(1-p.sub.3)=0.54 PA0 q.sub.2 =p.sub.1 *p.sub.3 +(1-p.sub.1)(1-p.sub.3)=0.5 PA0 q.sub.3 =p.sub.1 *p.sub.2 +(1-p.sub.1)(1-p.sub.2)=0.5 PA0 r.sub.1 =p.sub.1 *q.sub.1 /(p.sub.1 *q.sub.1 +(1-p.sub.1)(1-q.sub.1))=0.54 PA0 r.sub.2 =p.sub.2 *q.sub.2 /(p.sub.2 *q.sub.2 +(1-p.sub.2)(1-q.sub.2))=0.6 PA0 r.sub.3 =p.sub.3 *q.sub.3 /(p.sub.3 *q.sub.3 +(1-p.sub.3)(1-q.sub.3))=0.7 PA0 i i p PA0 i i p PA0 p p p PA0 p.fwdarw.1: LLR.fwdarw.+.infin. (approaching certainty) PA0 p=0.5: LLR=0 (no information) PA0 p.fwdarw.0: LLR.fwdarw.-.infin. (approaching impossibility) PA0 (a) producing first output log-probability quantities using a max-log-APP process based on a constraint set, each of said first output log-probability quantities corresponding to an input log-probability quantity from the input log-probability quantities; PA0 (b) computing a first extrinsic information value for each first output log-probability quantity from the first output log-probability quantities, said extrinsic information value computed as the difference between said output log-probability quantity and the corresponding input log-probability quantity; PA0 (c) for each first extrinsic information value, producing a corresponding second extrinsic information value based on the first extrinsic information values, PA0 (d) adding each of said second extrinsic information values to the corresponding input log-probability quantity to provide second output log-probability quantities. PA0 for each even-parity set, storing extrinsic information in the form of a minimum magnitude value, a second magnitude value, a location index associated with the minimum magnitude value, and a sign bit for each bit in the even-parity set.
It is evident that the probabilities associated with the second and third bit did not change as a result of APP processing. This is because the input probability for the first bit is 0.5, which means that any subset of bits that includes the first bit cannot provide any useful parity information and hence q.sub.2 and q.sub.3 are both 0.5.
Generally, for calculations performed by an APP process, it is assumed that the input probabilities do not incorporate the structural knowledge that the APP process is using as a basis for adjusting the input probabilities. In the above three-bit example, the calculations performed by the APP process assume that the three input probabilities do not incorporate the knowledge that the three bits have even parity. This is not to say that APP processing cannot be used when these underlying assumptions are not satisfied, only that the APP calculations are based on these assumptions. APP processing is often used, and can be highly effective, even when the underlying independence assumptions are not completely satisfied.
APP processing is commonly applied in an iterative manner. A brief description of iterative APP processing is as follows. Consider partitioning the constraints that define the relationships between entities being processed into two or more disjoint subsets. Further, assume that at least some of the entities involved in any given constraint subset are involved in some other constraint subset. That is, the subsets of entities that are associated with the subsets of constraints are overlapping subsets. It will also be assumed that the subsets of entities overlap in such a way so that all entities are affected, either directly or indirectly, by all constraints. Otherwise, a subset of entities and associated constraints could be extracted from the larger problem and processed on their own. Now, if each of the subsets of constraints is processed individually, information garnered from the processing of one subset of constraints can be used in the processing of subsequent constraint subsets. After all constraint subsets have been processed, the first constraint subset is returned to, and the overall process can be repeated. The processing of all of the constraint subsets is then repeated for an arbitrary number of iterations. Such an iterative processing approach is a useful tool in solving problems for which it is either impractical or impossible to consider all constraints simultaneously.
The following example of iterative processing is helpful in understanding the advantages thereto. APP processing is applied in an iterative manner to decode an error-correcting code structure that is represented as a two-dimensional array of bits where every row in the array has even parity and every column in the array has even parity. Such a code is pictured as follows:
The `i` letters represent information bits, and the `p` letters represent parity bits. The encoder sets the parity bits so as to make every row have even parity--each row has an eaten number of `1` bits, and to make every column have even parity. After transmission over a noisy channel, a modem demodulator produces probability estimates indicating the likelihood of each of these bits being a `0` bit or a `1` bit, based on the channel information only, without regard to the code structure introduced by the encoder. APP decoding starts with these probability estimates, and using the knowledge that each row of bits was transmitted with even parity, generates improved probability estimates for all of the bits. These improved probability estimates are used as inputs into APP processing for the columns, producing even more reliable probability estimates. The process is repeated, iterated, for a number of iterations. The number of iterations is predetermined, arbitrary, or determined based on a stopping criteria. After the first complete iteration of APP processing of the rows and then the columns, subsequent APP processing operates on input probabilities that do not completely satisfy the independence assumptions inherent in the APP calculations; nonetheless, additional APP processing iterations generally improve decoding performance. After an appropriate number of APP processing iterations, decoding is stopped and decisions about the bits are made based on the final probability values calculated during APP processing, or the soft outputs are passed on to a further process. The term "iterative processing" is used even when only one, or a partial, iteration is performed.
The mathematical details of APP processing are described in the literature; for example, see J. Erfanian, S. Pasupathy, G. Gulak, "Reduced complexity symbol detectors with parallel structures for ISI channels", IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp. 1661-1671, February/March/April 1994. For a discussion of APP processing in the context of iterative decoding of error-correcting codes, see J. Hagenauer, E. Offer, and L. Papke, "Iterative decoding of binary block and convolutional codes", IEEE Transactions on Information Theory, Vol. 42, No. 2, pp. 429-445, March 1996.
Log-APP
Log-APP is a form of APP processing where the quantities manipulated are not probabilities, but rather "log-probability quantities" derived from probabilities. The term "log-probability quantity," in the context of this document, refers to log-probabilities, log-probabilities with offsets, sums of log-probabilities, differences of log-probabilities, and combinations of these. Note that a "log-probability" is simply the logarithm of a probability; the base of the logarithm is arbitrary. Standard log-APP processing, without any approximations or enhancements, is, in mathematical terms, exactly equivalent to APP processing. In FIG. 1 the following definitions apply with reference to iterative log-APP processing and iterative max-log-APP processing:
L.sub.in represents a set of two or more input log-probability quantities; PA1 L.sub.out represents a set of two or more output log-probability quantities; and, PA1 L.sub.ex represents a set of two or more output extrinsic values. PA1 at least one of the second extrinsic information values being smaller in magnitude than the corresponding first extrinsic information value, and PA1 wherein said second extrinsic information value and the corresponding first extrinsic information value correspond to a same input log-probability quantity; and,
The feedback branches are only followed when iterative processing is performed with more than 1 iteration.
Manipulating log-probability quantities, rather than working with the probabilities themselves, is generally preferred due to computational issues such as the finite-precision representation of numbers. Also, in some sense, log-probability quantities are more "natural" quantities to work with than probabilities, as log-probability quantities represent "information", and log-APP processing then amounts to adding extra "information" to the input "information." This is well known to those of skill in the art in the field of "Information Theory".
Log-likelihood ratios
A common log-probability quantity used in log-APP processing is a "log-likelihood ratio" (LLR), which is a logarithm of a probability ratio; that is, a difference between two log-probabilities. Log-likelihood ratios (LLRs) are often convenient log-probability quantities to use. Consider the case where the entities being manipulated are bits. For this case, the log-likelihood ratio for a particular bit being a `0` bit is defined as: EQU LLR.sub.bit =log(p/(1-p))
where "p" is the probability of the bit in question being a `0` bit. Observe that such a "log-likelihood ratio" has the following properties:
Though the example above illustrates a way of using LLRs with binary entities (i.e. bits, which can only be either `0` or `1`), the concept of log-likelihood ratios is not restricted to this simple case and can be applied to M-ary symbols, states, and so forth. When the entities being considered are any of "M" choices, at most M-1 log-likelihood ratios are needed to fully describe the likelihoods associated with any particular entity. For example, with an 8-ary symbol alphabet, no more than 7 LLRs are required to fully characterize the probabilities associated with any particular symbol.
Max-log-APP
"Max-log-APP" is a form of log-APP processing where some or all calculations of expressions of the form log.sub.b (b.sup.x +b.sup.y) are approximated as simply log.sub.b (b.sup.x +b.sup.y).about.max(x,y). The letter "b" is used to denote the base of the logarithm, which is arbitrary. The letters "x" and "y" represent the quantities being "combined", which are typically log-probability quantities having the same base "b". As an example, log.sub.e (e.sup.2 +e.sup.3), where e is the base for natural logarithms, would be approximated as simply "3", whereas the answer to three decimal places is 3.313. Introducing this approximation into the log-APP calculations generally results in a degradation of the results of an overall process of which the max-log-APP process is a part, but using the approximation can provide a significant reduction in computational complexity and thereby improve speed of processing. Max-log-APP processing is not, in mathematical terms, equivalent to standard log-APP processing, but is an approximation thereto.
It may not be immediately apparent that a given process is indeed a max-log-APP process. For example, consider a process that operates in the following manner. The input to the process is a set of estimates associated with a set of bits known to have even parity. Positive estimates indicate that a bit is more likely to be a `0` than a `1`, and conversely, negative estimates indicate that a bit is more likely to be a `1` than a `0`. The process first establishes the "parity" of the set of input bit estimates by counting how many of the input values are negative. When an even number of these values are negative, the set of input estimates is considered to have even parity, and when an odd number are negative, then the set of input estimates is considered to have odd parity and includes at least one bit in error. Using this parity result, the process then either "strengthens" or "weakens" each input bit estimate to produce the corresponding output bit estimate. An input bit estimate is "strengthened" when the overall parity is even, and "weakened" when the overall parity is odd. The magnitude of the strengthening or weakening for each bit is determined by the smallest magnitude of all of the input estimates, excluding the estimate associated with the bit under consideration. Referring to FIG. 3, an illustration of the operation of this soft-in soft-out (SISO) process is shown. "Soft-in soft-out" is used here to mean that the process accepts as input, and produces as output, estimates of, rather than decisions about, entities being considered.
Though not immediately apparent, this process is in fact a max-log-APP process. A proof of this relationship is not presented here in order to avoid unnecessary detail, but the proof is determinable as follows. One begins with the log-APP calculations for a set of bits having even parity using log-likelihood ratios as the quantities being manipulated, introduce the "max" approximation throughout, and then simplify. The end result is a process similar to that described above. This example shows how simple some log-APP processes become when the "max" approximation is employed and helps to highlight the advantages of their implementation.
Analysing a max-log-APP process beginning with its simplified form, rather than beginning with its non-approximated log-APP origin, often provides useful insight into how the process operates, and how this operation differs from true log-APP processing. For example, consider a bit-wise max-log-APP process for a binary convolutional code. In many cases, such a process is thought of as determining, for each bit for which a soft output is desired, two path metrics: the path metric of the most likely sequence having a `0` bit in the position being considered, and the path metric of the most likely sequence having a `1` bit in the position being considered, and then using these two path metrics to calculate an "improved" estimate for the bit. That is, instead of using all possible paths, only two paths are used to calculate the output for any given bit position: the best `0`-bit path, and the best `1`-bit path.
Discussions on max-log-APP processing are found in the literature; for example, see J. Erfanian, S. Pasupathy, G. Gulak, "Reduced complexity symbol detectors with parallel structures for ISI channels", IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp. 1661-1671, February/March/April 1994.
Extrinsic information
The term "extrinsic information" is used herein to refer to a difference between output values and input values of a log-APP process including a max-log-APP process. Specifically, for any given entity upon which the log-APP process operates, the difference between the associated output log-probability quantity and the corresponding input log-probability quantity is termed the "extrinsic information" for the given entity, for the log-APP process being considered. Note that in determining this difference between the output log-probability quantity and the input log-probability quantity, the output log-probability quantity is expressed in a form that is consistent with that used for the input log-probability quantity. That is, the output log-probability quantity is expressed in such a way so that it is interpretable in the same way as the input log-probability quantity, and hence the output log-probability quantities are comparable directly with the input log-probability quantities.
For convenience, the extrinsic information associated with a given log-APP process is referred to as being "produced" by the process.